/*
*	Ivan Concua 12352
*	Roberto Andrino 12413
*	Algoritmos y estructuras de datos
*	Probabilidades.java
*	
*/
package lab7;

/**
 *
 *
 */
//crea el arbol estableciendo las raices
public class Huff {
// alphabet size of extended ASCII
    private static final int R = 256;
   String arbol="";
    // Huffman trie node
    NodoHuffman root1 = new NodoHuffman(' ',2,null,null);


    // compress bytes from standard input and write to standard output
    public String compress(String cadena) {
        // read the input
        String res="";
        char[] input = cadena.toCharArray();

        // tabulate frequency counts
        int[] freq = new int[R];
        for (int i = 0; i < input.length; i++){
            
            freq[input[i]]++;
            
        }
        // build Huffman trie
        NodoHuffman root = buildTrie(freq);
        root1=root;
        // build code table
        String[] st = new String[R];
        buildCode(st, root, "");
        
        //impresion de la tabla
        
        // use Huffman code to encode input
        for (int i = 0; i < input.length; i++) {
            String code = st[input[i]];
            String minicadena="";
            
            for (int j = 0; j < code.length(); j++) {
                if (code.charAt(j) == '0') {
                    minicadena=minicadena+'0';
                }
                else if (code.charAt(j) == '1') {
                    minicadena=minicadena+'1';
                }
                else throw new IllegalStateException("Illegal state");
            }
           
            res=res+minicadena;
            System.out.println("A la letra "+input[i]+" le corresponde el codigo "+ minicadena);
        }

        // close output stream
        return res;
    }

    


    // write bitstring-encoded trie to standard output
  

    // make a lookup table from symbols and their encodings
    private static void buildCode(String[] st, NodoHuffman x, String s) {
        if (!x.isLeaf()) {
            buildCode(st, x.left,  s + '0');
            buildCode(st, x.right, s + '1');
        }
        else {
            st[x.ch] = s;
        }
    }
    // build the Huffman trie given frequencies
    private static NodoHuffman buildTrie(int[] freq) {

        // initialze priority queue with singleton trees
        MinPQ<NodoHuffman> pq = new MinPQ<NodoHuffman>();
        for (char i = 0; i < R; i++)
            if (freq[i] > 0)
                pq.insert(new NodoHuffman(i, freq[i], null, null));

        // merge two smallest trees
        while (pq.size() > 1) {
            NodoHuffman left  = pq.delMin();
            NodoHuffman right = pq.delMin();
            NodoHuffman parent = new NodoHuffman('\0', left.freq + right.freq, left, right);
            pq.insert(parent);
        }
        return pq.delMin();
    }
    
    public String expand(String cadena) {

        // read in Huffman trie from input stream
        
        String res="";
        // number of bytes to write
        char[] cad=cadena.toCharArray();
        int length = cad.length;
        NodoHuffman x = root1;
        // decode using the Huffman trie
        for (int i = 0; i < length; i++) {
            
            if (!x.isLeaf()) {
                
                char bit = cad[i];
                if (bit=='1') x = x.right;
                else     x = x.left;
                if(x.isLeaf()){
                    res=res+x.ch;
                    x=root1;
                }
            }
        }
       return res;
    }

    // expand Huffman-encoded input from standard input and write to standard output
    


   


    
}